const data = [
	{
		node_id: 1,
		parent_id: 0,
		name: '一级1.0.1',
	},
	{
		node_id: 2,
		parent_id: 0,
		name: '一级1.0.2',
	},
	{
		node_id: 3,
		parent_id: 1,
		name: '二级2.1.3',
	},
	{
		node_id: 7,
		parent_id: 1,
		name: '二级2.1.7',
	},
	{
		node_id: 6,
		parent_id: 7,
		name: '三级3.7.6',
	},
	{
		node_id: 5,
		parent_id: 7,
		name: '三级3.7.5',
	},
]

/**
 * @description: 一维数组 转 树结构 一
 * @param {data}  源数据
 * @param {parent_id}  父级id
 * @return {list} tree结构
 */
function arr2tree(data, parent_id) {
	var tree = []
	data.forEach(item => {
		if (item.parent_id === parent_id) {
			item.children = arr2tree(data, item.node_id)
			tree.push(item)
		}
	})
	return tree
}
// console.log(arr2tree(data, 0));

/**
 * @description: 一维数组 转 树结构 二 , 利用引用地址
 * @param {list} 源数据
 * @return {res}  tree结构
 */
function arr2tree2(list) {
	const res = []
	const map = list.reduce((a, b) => {
		a[b.node_id] = b
		return a
	}, {})
	for (const item of list) {
		if (item.parent_id === 0) {
			res.push(item)
			continue
		}
		if (item.parent_id in map) {
			const parent = map[item.parent_id]
			parent.children = parent.children || []
			parent.children.push(item)
		}
	}
	return res
}
// console.log(arr2tree2(data));

/**
 * 树结构 转 一维数组
 */
function tree2arr(tree) {
	let arr = []
	tree.forEach(v => {
		if (v.children) {
			arr = arr.concat(...tree2arr(v.children))
		}
		delete v.children
		arr.push(v)
	})
	return arr
}
// console.log(tree2arr(tree));

/**
 * 数组转树形结构,时间复杂度O(n) 和上面的arr2tree2类似，形参代替具体的节点id，更好一点
 * @param list 数组
 * @param idKey 元素id键
 * @param parIdKey 元素父id键
 * @param parId 第一级根节点的父id值
 * @return {[]}
 */
console.log(listToTree(data, 'node_id', 'parent_id', 0))
function listToTree(list, idKey, parIdKey, parId) {
	let map = {}
	let result = []
	let len = list.length

	// 构建map
	for (let i = 0; i < len; i++) {
		//将数组中数据转为键值对结构 (这里的数组和obj会相互引用，这是算法实现的重点)
		map[list[i][idKey]] = list[i]
	}

	// 构建树形数组
	for (let i = 0; i < len; i++) {
		let itemParId = list[i][parIdKey]
		// 顶级节点
		if (itemParId === parId) {
			result.push(list[i])
			continue
		}
		// 孤儿节点，舍弃(不存在其父节点)
		if (!map[itemParId]) {
			continue
		}
		// 将当前节点插入到父节点的children中（由于是引用数据类型，obj中对于节点变化，result中对应节点会跟着变化）
		if (map[itemParId].children) {
			map[itemParId].children.push(list[i])
		} else {
			map[itemParId].children = [list[i]]
		}
	}
	return result
}
